package se.boliang.Q01;

public class DSTransform {
	
	private BinaryTreeNode headNode, tailNode;
	
	public DSTransform() {
		headNode = new BinaryTreeNode(0, null, tailNode); 
		tailNode = new BinaryTreeNode(100, headNode, null); 
	}

	public void doDSTransform(BinaryTreeNode curNode) {

		if (curNode == null)
			return;

		doDSTransform(curNode.getLeftChildNode());
		
		/**
		 * the structure of doubly linked list is as follows:
		 * (head -- Node04 -- ... -- Node16 -- tail)
		 * When new node is popped:
		 * 1. let new node left points to tail's left child
		 * 2. let tail's left child right points to new node
		 * so it finishes new node's left relationship in the doubly linked list
		 * 3. let tail node left points to the new node
		 */
		curNode.setLeftChildNode(tailNode.leftChildNode); 
		tailNode.getLeftChildNode().setRightChildNode(curNode); 
		tailNode.setLeftChildNode(curNode); 

		
		doDSTransform(curNode.getRightChildNode());

	}
	


	public void doPrintDoublyLinkedList(BinaryTreeNode rootNode) {
		
		this.doDSTransform(rootNode); 
		System.out.print("Print from Doubly Linked List: "); 
		BinaryTreeNode curNode = headNode.getRightChildNode(); 
		while (curNode != null) {
			System.out.print(curNode.getNodeValue() + " "); 
			curNode = curNode.getRightChildNode();
		}
	}
}
